一.定义
第二类斯特林数 {nm} 表示把 n 个不同的小球放进 m 个相同的盒子里,不能有空盒的方案数。
一些小性质:
- {n0}=[n=0]
- 当 n<m ,{nm}=0
二.一些等式
1. 递推式:{nm}={n−1m−1}+m{n−1m}
对第 n 个球的放法讨论
- 单独放一个盒子,方案为 {n−1m−1}
- 与其他球放在一个盒子,因为盒子不同有 m 种选法,每种选法方案为 {n−1m}
2.自然幂数和:mn=∑i=0n{ni}mi=∑i=0n{ni}(im)i!
1.组合意义
左式为将 n 不同的小球放进 m 个不同的盒子里。
右式枚举非空盒子的数量 i,选盒子的方案数为 (im) , 将 n 个不同的球放入 i 个盒子方案数为 {ni},因为盒子不同所以有 i! 种排列。
2.例题
3.通项公式:{nm}=m!1∑i=0m(−1)i(im)(m−i)n
1.证明
设 f(m)=mn,g(m)={nm}m!。
那么有: f(m)=∑i=0m(im){ni}i!=∑i=0m(im)g(i)
这里上界为 m 不影响答案,因为 n<m 时 {ni}=0。
然后由二项式反演得: g(m)=∑i=0m(−1)m−i(im)f(i)
{nm}m!=i=0∑m(−1)m−i(im)in
{nm}=m!1i=0∑m(−1)m−i(im)in
{nm}=m!1i=0∑m(−1)i(im)(m−i)n
{nm}m!=i=0∑m(−1)m−i(im)in
{nm}m!=i=0∑m(−1)m−ii!(m−i)!m!in
{nm}=i=0∑mi!(m−i)!(−1)m−iin
{nm}=i=0∑mi!in(m−i)!(−1)m−i
可以看出是一个卷积形式,用多项式乘法可 O(nlogn) 求出第二类斯特林数的任意一行。
三.生成函数